Graph Neural Networks

Author

Your Name

Published

January 28, 2025

Introduction

This document provides an in-depth overview of Graph Neural Networks (GNNs), a powerful class of neural networks designed to operate on graph-structured data. Unlike traditional neural networks that process data in a linear fashion, GNNs leverage the inherent structure of graphs to capture complex relationships between entities. This lecture covers the fundamental concepts of graphs, the architecture of GNNs, various prediction tasks they can handle, and the intricacies of the message-passing paradigm.

The main objectives of this lecture are:

To understand the motivation behind using GNNs and how they differ from linear models.
To learn the core concepts of graph theory, including nodes, edges, and global graph attributes.
To explore how information is encoded within graphs at different levels (node, edge, and graph).
To examine various types of graph-based prediction tasks.
To delve into the architecture of GNNs, focusing on the message-passing paradigm and pooling strategies.
To understand the implementation details of message passing and address common challenges.

By the end of this lecture, you should have a solid understanding of GNNs and be able to appreciate their applications in various domains.

Introduction to Graph Neural Networks

Shifting from Linear to Graph-Based Models

Traditional neural networks, including convolutional neural networks and transformers, process data in a linear sequence. They start with an input, process it through a series of components, and produce an output. This linear flow is illustrated in Figure 1. Even architectures like ResNet, which incorporate skip connections (allowing information to bypass certain layers), maintain an overall linear progression of data. These skip connections can be thought of as shortcuts that help mitigate the vanishing gradient problem in deep networks, but they do not fundamentally alter the sequential nature of the data flow.

Linear Flow in Traditional Neural Networks

Graph Neural Networks (GNNs), however, break away from this linearity by operating on graphs. In a graph, the processing flow is determined by the graph’s structure rather than a predefined sequence, as depicted in Figure 2. This allows GNNs to capture complex relationships and dependencies that are inherent in graph-structured data.

Non-linear Flow in Graph Neural Networks

Core Graph Concepts

Nodes, Edges and Graphs

A graph $G = (V, E)$ is fundamentally defined by its nodes (vertices) $V$ and the edges $E$ that connect them. Nodes represent entities, while edges represent the relationships between these entities.

Nodes (Vertices) ($V$): Entities within the graph.
Edges ($E$): Connections between nodes, representing relationships. An edge $e_{ij} \in E$ connects node $v_i$ to node $v_j$, where $v_i, v_j \in V$.

Global Graph Attributes

In addition to nodes and edges, a graph can also have global attributes ($u$) that describe the graph as a whole. These attributes provide context or summary information about the entire graph, such as the overall topic of a social network or the chemical properties of a molecule.

Encoding Information within Graphs

Information within a graph can be encoded at three different levels, as shown in Figure 3:

Encoding Information in Graphs: Nodes, Edges, and Global Attributes

Node-Specific Features

Each node $v_i$ can have associated features $x_i$ that describe its properties. For example, in a social network, node features might include a user’s name, age, location, and other personal details. These features are typically represented as a vector.

Edge-Specific Features

Edges can also carry information, representing the nature or strength of the relationship between nodes. For instance, in a social network, edge features $e_{ij}$ might indicate the number of interactions, the type of relationship (e.g., friend, family), or the duration of the connection between two users $v_i$ and $v_j$.

Global Graph-Level Features

Global features ($u$) provide information about the entire graph. For example, in a social network, a global feature might indicate the geographic location, the overall density of connections, or the main topic of discussion within the network. In a molecule, it could represent properties like overall polarity or energy.

Examples of Graph Data

Graphs are versatile and can represent various types of data:

Molecular Structures

Molecules can be represented as graphs, with atoms as nodes and bonds as edges. Node features can describe atom type, charge, etc., while edge features can represent bond type and strength. This representation is crucial in fields like drug discovery and materials science, where understanding molecular structure is essential for predicting properties and interactions.

Representing Images as Graphs

Images can be represented as graphs, although this is less common due to the success of specialized models like convolutional neural networks. One possible approach is to represent pixels as nodes and connect neighboring pixels with edges, forming a grid-like graph. However, the regularity of this structure is often better handled by CNNs. Another approach is to segment the image into regions (superpixels) and represent these regions as nodes, with edges connecting adjacent regions. This can be useful for tasks like image segmentation or object recognition.

Representing Text as Graphs

Text can be represented as a graph where words are nodes and connections represent relationships between words, such as syntactic dependencies or co-occurrence in a sentence. However, the effectiveness of this approach compared to specialized models like transformers is debated, as transformers are specifically designed to capture sequential and contextual information in text.

Graph-Based Prediction Tasks

GNNs can be used for various prediction tasks, depending on the level at which the prediction is made: node, edge, or the entire graph.

Graph-Level Prediction Tasks

In graph-level tasks, the goal is to predict a property of the entire graph. The prediction is based on the aggregated information from all nodes and edges within the graph.

Molecule Classification: Predicting whether a molecule is toxic or has a specific pharmacological property (e.g., antibiotic, antiviral) based on its molecular graph structure. For example, given a graph representing the structure of a molecule, the task might be to predict if the molecule will smell pungent or not.
Material Property Prediction: Determining the stability, conductivity, or other physical properties of a material based on its atomic structure represented as a graph.
Social Network Analysis: Classifying a social network based on its overall characteristics, such as identifying a network as a community of sports enthusiasts or a political discussion group. For example, given the graph of a social network in Africa, predict global properties of this network.
Program Analysis: Predicting properties of a program’s control flow graph, such as whether it contains certain types of bugs or security vulnerabilities.
Drug Discovery: Given the molecular graph of a drug, predict whether it will be effective against a specific disease.

Example Visualization:

Node-Level Prediction Tasks

Node-level tasks involve predicting properties of individual nodes within a graph. The prediction for each node is based on its features and its relationship with neighboring nodes.

User Classification in Social Networks: Predicting the demographics, interests, or preferences of a user in a social network based on their profile and connections. For example, predicting whether a user in the network will follow a particular user (e.g., "High" or "John") based on their connections and interactions.
Node Role Identification: Determining the role or function of a node in a network, such as identifying influential users in a social network or critical components in an infrastructure network.
Protein Function Prediction: Predicting the function of a protein in a protein-protein interaction network based on its interactions with other proteins.
Fraud Detection: Identifying suspicious users or accounts in a financial network based on their transaction patterns and connections.

Example Visualization:

Edge-Level Prediction Tasks

Edge-level tasks focus on predicting properties of edges or the existence of edges within a graph. This can involve predicting the type of relationship between two nodes, the strength of the connection, or whether a connection should exist at all.

Link Prediction in Social Networks: Predicting whether two users in a social network will become friends or whether a user will follow another user.
Relationship Prediction: Determining the type of relationship between two entities, such as predicting whether two people are colleagues, family members, or friends.
Image Segmentation Relationship Prediction: In an image segmented into regions, predicting the relationship between regions, such as whether one region is "part of" another or whether two regions are "adjacent to" each other. For example, given an image, extract the semantic segmentation and then predict the relationship between the entities in the image.
Knowledge Graph Completion: Predicting missing relationships between entities in a knowledge graph.

Example Visualization:

Graph Neural Network Architecture

Overall Structure and Workflow

A Graph Neural Network (GNN) takes a graph $G = (V, E)$ as input, where $V$ represents the set of nodes and $E$ represents the set of edges. It processes the graph through a series of layers (or blocks), as illustrated in Figure 4. Each layer transforms the graph’s features while preserving its underlying structure. The output is a transformed graph with updated node, edge, and/or global features.

GNN Workflow: Input graph is processed through multiple GNN layers, resulting in a transformed graph with updated features.

The connectivity of the graph remains the same throughout the process; that is, the set of nodes $V$ and edges $E$ are unchanged. However, the features associated with nodes ($X$), edges ($E$), and the global graph ($u$) are updated by each GNN layer.

The Message Passing Paradigm

The core of GNN operation is the **message-passing paradigm**. In this paradigm, nodes update their embeddings (feature representations) by iteratively aggregating information from their neighbors. This process can be visualized as nodes sending "messages" to each other, where each message carries information about the sender’s current state.

Updating Node Embeddings via Message Passing

In a single message-passing step, each node $v_i$ updates its embedding $x_i^{(l+1)}$ at layer $l+1$ by considering its own current embedding $x_i^{(l)}$ at layer $l$ and the embeddings of its neighbors $x_j^{(l)}$, where $j \in \mathcal{N}(i)$ and $\mathcal{N}(i)$ denotes the set of neighbors of node $i$.

Neighborhood Aggregation Techniques

The aggregation of information from neighboring nodes can be done using various methods. Common aggregation functions include:

Sum: Summing the embeddings of neighboring nodes: $\sum_{j \in \mathcal{N}(i)} x_j^{(l)}$
Mean: Averaging the embeddings of neighboring nodes: $\frac{1}{|\mathcal{N}(i)|} \sum_{j \in \mathcal{N}(i)} x_j^{(l)}$
Max: Taking the element-wise maximum of neighboring node embeddings: $\max_{j \in \mathcal{N}(i)} x_j^{(l)}$
Attention-based: Using an attention mechanism to weigh the importance of each neighbor’s contribution, as described in Graph Attention Networks (GATs).

Transformation with Neural Networks

After aggregating the neighborhood information, a neural network is applied to transform the aggregated embedding. This introduces non-linearity and allows the model to learn complex patterns in the graph data. The update rule for node $v_i$ at layer $l+1$ can be generally expressed as:

\[x_i^{(l+1)} = f^{(l+1)}\left(x_i^{(l)}, \text{AGGREGATE}\left(\{x_j^{(l)} : j \in \mathcal{N}(i)\}\right)\right)\]

where:

$x_i^{(l+1)}$ is the updated embedding of node $v_i$ at layer $l+1$.
$x_i^{(l)}$ is the embedding of node $v_i$ at layer $l$.
$\mathcal{N}(i)$ is the set of neighbors of node $i$.
$\text{AGGREGATE}$ is an aggregation function (e.g., sum, mean, max).
$f^{(l+1)}$ is a neural network specific to layer $l+1$, which transforms the concatenated or combined embeddings.

Pooling Strategies for Making Predictions

After applying several GNN layers, we obtain a transformed graph with updated embeddings. To make predictions, we need to use these embeddings. The strategy for using these embeddings depends on the type of prediction task.

Node-Level Prediction

For node-level tasks, we can directly use the final node embeddings. A classifier (e.g., a neural network) can be applied to each node’s embedding to predict its label or property.

Input: Transformed graph $G_N = (V, E, X_N, E_N, u_N)$, Classifier $C$ Output: Node predictions $y_i$ for each node $i \in V$ $y_i = C(x_i^N)$

Pooling from Edges to Nodes for Node-Level Prediction

When node-level predictions are needed, but only edge information is available, we can aggregate information from edges to create node embeddings. This process is called **edge-to-node pooling**.

Input: Graph $G = (V, E)$, Edge embeddings $e_{ij}$ for each edge $(i, j) \in E$ Output: Node embeddings $x_i$ for each node $i \in V$ Initialize an empty set $S_i$ Add $e_{jk}$ to $S_i$ $x_i = \text{AGGREGATE}(S_i)$

The complexity of this algorithm is $O(|V| + |E|)$, as we iterate through all nodes and edges in the worst case.

Pooling from Nodes to Edges for Edge-Level Prediction

Similarly, when edge-level predictions are needed, but only node information is available, we can aggregate node embeddings to create edge embeddings. This is called **node-to-edge pooling**.

Input: Graph $G = (V, E)$, Node embeddings $x_i$ for each node $i \in V$ Output: Edge embeddings $e_{ij}$ for each edge $(i, j) \in E$ $e_{ij} = \text{COMBINE}(x_i, x_j)$

The complexity of this algorithm is $O(|E|)$, as we iterate through all edges.

Pooling for Global Graph-Level Prediction

To make predictions about the entire graph, we need to create a global graph embedding. This can be achieved by aggregating node or edge embeddings. This process is called **graph-level pooling**.

Input: Graph $G = (V, E)$, Node embeddings $x_i$ for each node $i \in V$ Output: Global graph embedding $u$ Initialize an empty set $S$ Add $x_i$ to $S$ $u = \text{AGGREGATE}(S)$

The complexity of this algorithm is $O(|V|)$, as we iterate through all nodes.

Note: The choice of aggregation function (AGGREGATE) and combination function (COMBINE) depends on the specific task and the nature of the data. Also, after applying pooling strategies, a classifier can be used to make the final prediction. For example, after graph-level pooling, a neural network can be used to predict the graph’s label.

Message Passing Implementation

Representing Graph Data for Computation

To implement message passing in a GNN, we need efficient ways to represent the graph structure and the features associated with its nodes and edges.

Node Embeddings

Each node $v_i \in V$ is represented by an embedding vector $x_i \in \mathbb{R}^{d}$, where $d$ is the dimensionality of the embedding space. This vector encodes the features of the node. For a graph with $n$ nodes, we can represent all node embeddings as a matrix $X \in \mathbb{R}^{n \times d}$, where each row corresponds to the embedding of a node.

Adjacency Matrix Representation

The adjacency matrix $A \in \mathbb{R}^{n \times n}$ is a square matrix that encodes the connections between nodes in the graph. It is defined as:

\[A_{ij} = \begin{cases} 1, & \text{if } (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases}\]

where $A_{ij}$ is the element in the $i$-th row and $j$-th column of $A$, and $(v_i, v_j) \in E$ indicates the presence of an edge between nodes $v_i$ and $v_j$.

Degree Matrix Representation

The degree matrix $D \in \mathbb{R}^{n \times n}$ is a diagonal matrix where each diagonal element $D_{ii}$ represents the degree of node $v_i$, which is the number of edges connected to it. Formally:

\[D_{ii} = \sum_{j=1}^{n} A_{ij}\]

Challenges with Basic Aggregation Methods

While the basic message-passing idea is powerful, straightforward implementations can face certain challenges:

Lack of Self-Information in Aggregation

A simple aggregation of neighbor embeddings, such as $\sum_{j \in \mathcal{N}(i)} x_j$, might ignore the node’s own features during the update. This can lead to a loss of information about the node itself. For example, if we only consider the neighbors’ embeddings, the updated embedding of a node might not reflect its initial features, leading to a misrepresentation of the node’s identity in the graph.

Potential for Exploding Values

Repeatedly summing embeddings across multiple message-passing layers can lead to very large values in the node embeddings. This can cause numerical instability during training and negatively impact the model’s performance. Specifically, if the sum of embeddings is not normalized, the magnitude of the embeddings can grow exponentially with each layer, making the optimization process unstable.

Addressing the Challenges

Incorporating Self-Connections

To ensure that a node’s own features are considered during aggregation, we can add self-loops to the graph. This is achieved by adding the identity matrix $I$ to the adjacency matrix $A$, creating a new adjacency matrix $\tilde{A}$:

\[\tilde{A} = A + \lambda I\] Here, $\lambda$ is a hyperparameter that controls the weight given to the node’s own features. When $\lambda = 1$, it’s equivalent to adding a single self-loop to each node.

Now, when aggregating neighbor information, the node’s own embedding will also be included in the sum, weighted by $\lambda$.

Normalization using the Degree Matrix

To prevent the explosion of values during repeated aggregation, we can normalize the aggregation by the node degrees. A common approach is to multiply the adjacency matrix by theinverse of the degree matrix. This leads to a normalized adjacency matrix:

\[\hat{A} = D^{-1}A\]

Now, instead of summing the neighbor embeddings, we are effectively taking their average.

More advanced normalization techniques, such as the one used in Graph Convolutional Networks (GCNs), use a symmetrically normalized adjacency matrix:

\[\hat{A} = D^{-\frac{1}{2}} \tilde{A} D^{-\frac{1}{2}}\]

This normalization considers both the degree of the central node and the degrees of its neighbors. The use of $D^{-\frac{1}{2}}$ on both sides helps to scale the embeddings proportionally to the square root of thenode degrees, which can further stabilize training.

Let’s consider a simple message-passing update rule using the normalized adjacency matrix with self-connections:

\[X^{(l+1)} = \sigma(\hat{A} X^{(l)} W^{(l)})\]

where:

$X^{(l)}$ is the matrix of node embeddings at layer $l$.
$W^{(l)}$ is the weight matrix for layer $l$. This matrix is learned during training and transforms the aggregated embeddings.
$\sigma$ is an activation function (e.g., ReLU).
$\hat{A} = D^{-\frac{1}{2}} (A + I) D^{-\frac{1}{2}}$ is the normalized adjacency matrix with self-connections.

This update rule first adds self-connections to the graph, then normalizes the adjacency matrix, performs a weighted aggregation of neighbor embeddings (including the node’s own), and finally applies a non-linear transformation using the learned weight matrix $W^{(l)}$.

Iterative Message Passing and Neighborhood Scope

By iteratively applying message passing, the model can propagate information across the graph. Each iteration allows nodes to incorporate information from a wider neighborhood. After $k$ iterations, a node’s embedding will contain information from nodes that are at most $k$ hops away in the graph.

Neighborhood scope after k iterations of message passing, starting from node 1.

Note: The number of message-passing iterations is a hyperparameter that needs to be tuned. Using too few iterations might limit the model’s ability to capture long-range dependencies, while using too many iterations can lead to over-smoothing, where node embeddings become too similar and lose their discriminative power. In practice, 2-4 layers are often sufficient based on empirical evidence.

A Concrete Example

Let’s consider a graph with 5 nodes and the following adjacency matrix $A$, degree matrix $D$, and initial node embeddings matrix $X^{(0)}$:

\[A = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix}, D = \begin{bmatrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}, X^{(0)} = \begin{bmatrix} -1.5 & 1.1 & 2.5 \\ 3.1 & -2.6 & 2.7 \\ -0.3 & 1.7 & -2.0 \\ 1.9 & -0.5 & 0.8 \\ 2.2 & -1.3 & 0.5 \end{bmatrix}\]

We’ll add self-loops ($\tilde{A} = A + I$) and compute the symmetrically normalized adjacency matrix:

\[\tilde{A} = A + I = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}\]

\[\tilde{D} = \begin{bmatrix} 3 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{bmatrix}\]

\[\hat{A} = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}\] We won’t compute the exact values of $\hat{A}$ here, but it will be a 5x5 matrix.

Now, let’s perform one step of message passing using the formula:

\[X^{(1)} = \sigma(\hat{A} X^{(0)} W^{(0)})\]

Suppose we have a randomly initialized weight matrix $W^{(0)} \in \mathbb{R}^{3 \times 2}$:

\[W^{(0)} = \begin{bmatrix} 0.5 & -0.2 \\ -0.3 & 0.4 \\ 0.1 & -0.1 \end{bmatrix}\]

We first compute the product $\hat{A} X^{(0)}$. This will result in a 5x3 matrix where each row represents the aggregated and normalized embedding of a node, considering its neighbors and itself. Then, we multiply this matrix by $W^{(0)}$ to get a 5x2 matrix. Finally, we apply an activation function $\sigma$ (e.g., ReLU) element-wise to obtain $X^{(1)}$.

After computing $X^{(1)}$, we can use it for node-level predictions or perform further message-passing steps.

Conclusion

Graph Neural Networks offer a powerful way to analyze and make predictions on graph-structured data. They leverage the inherent structure of graphs to capture complex relationships between entities, making them suitable for a wide range of applications, from social network analysis to drug discovery.

Key takeaways from this lecture include:

GNNs process data in a non-linear fashion, determined by the graph structure.
Information can be encoded at the node, edge, and graph levels.
GNNs can perform various prediction tasks at different levels of the graph.
The message-passing paradigm is central to GNN operation, allowing nodes to update their embeddings based on their neighbors.
Pooling strategies enable predictions at different levels by aggregating information.
Challenges like the lack of self-information and exploding values can be addressed through techniques like adding self-connections and normalization.

**Follow-up Questions:**

How might the choice of aggregation function (e.g., sum, mean, max) impact the performance of a GNN?
What are the trade-offs between using a deep GNN (many layers) versus a shallow one?
How can GNNs be adapted to handle directed graphs or graphs with multiple types of edges?
What are some real-world applications where GNNs have shown significant improvements over traditional methods?

This concludes the lecture on Graph Neural Networks. Further exploration and experimentation with different architectures and applications will deepen your understanding of this fascinating field.

--- title: "Graph Neural Networks" author: "Your Name" date: "2025-01-28" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This document provides an in-depth overview of Graph Neural Networks (GNNs), a powerful class of neural networks designed to operate on graph-structured data. Unlike traditional neural networks that process data in a linear fashion, GNNs leverage the inherent structure of graphs to capture complex relationships between entities. This lecture covers the fundamental concepts of graphs, the architecture of GNNs, various prediction tasks they can handle, and the intricacies of the message-passing paradigm. The main objectives of this lecture are: - To understand the motivation behind using GNNs and how they differ from linear models. - To learn the core concepts of graph theory, including nodes, edges, and global graph attributes. - To explore how information is encoded within graphs at different levels (node, edge, and graph). - To examine various types of graph-based prediction tasks. - To delve into the architecture of GNNs, focusing on the message-passing paradigm and pooling strategies. - To understand the implementation details of message passing and address common challenges. By the end of this lecture, you should have a solid understanding of GNNs and be able to appreciate their applications in various domains. # Introduction to Graph Neural Networks ## Shifting from Linear to Graph-Based Models Traditional neural networks, including convolutional neural networks and transformers, process data in a linear sequence. They start with an input, process it through a series of components, and produce an output. This linear flow is illustrated in Figure [1](#fig:linear_flow){reference-type="ref" reference="fig:linear_flow"}. Even architectures like ResNet, which incorporate skip connections (allowing information to bypass certain layers), maintain an overall linear progression of data. These skip connections can be thought of as shortcuts that help mitigate the vanishing gradient problem in deep networks, but they do not fundamentally alter the sequential nature of the data flow. <figure id="fig:linear_flow"> <figcaption>Linear Flow in Traditional Neural Networks</figcaption> </figure> Graph Neural Networks (GNNs), however, break away from this linearity by operating on graphs. In a graph, the processing flow is determined by the graph's structure rather than a predefined sequence, as depicted in Figure [2](#fig:graph_flow){reference-type="ref" reference="fig:graph_flow"}. This allows GNNs to capture complex relationships and dependencies that are inherent in graph-structured data. <figure id="fig:graph_flow"> <figcaption>Non-linear Flow in Graph Neural Networks</figcaption> </figure> ## Core Graph Concepts ### Nodes, Edges and Graphs A graph $G = (V, E)$ is fundamentally defined by its nodes (vertices) $V$ and the edges $E$ that connect them. Nodes represent entities, while edges represent the relationships between these entities. - **Nodes (Vertices) ($V$)**: Entities within the graph. - **Edges ($E$)**: Connections between nodes, representing relationships. An edge $e_{ij} \in E$ connects node $v_i$ to node $v_j$, where $v_i, v_j \in V$. ### Global Graph Attributes In addition to nodes and edges, a graph can also have global attributes ($u$) that describe the graph as a whole. These attributes provide context or summary information about the entire graph, such as the overall topic of a social network or the chemical properties of a molecule. ## Encoding Information within Graphs Information within a graph can be encoded at three different levels, as shown in Figure [3](#fig:graph_info){reference-type="ref" reference="fig:graph_info"}: <figure id="fig:graph_info"> <figcaption>Encoding Information in Graphs: Nodes, Edges, and Global Attributes</figcaption> </figure> ### Node-Specific Features Each node $v_i$ can have associated features $x_i$ that describe its properties. For example, in a social network, node features might include a user's name, age, location, and other personal details. These features are typically represented as a vector. ### Edge-Specific Features Edges can also carry information, representing the nature or strength of the relationship between nodes. For instance, in a social network, edge features $e_{ij}$ might indicate the number of interactions, the type of relationship (e.g., friend, family), or the duration of the connection between two users $v_i$ and $v_j$. ### Global Graph-Level Features Global features ($u$) provide information about the entire graph. For example, in a social network, a global feature might indicate the geographic location, the overall density of connections, or the main topic of discussion within the network. In a molecule, it could represent properties like overall polarity or energy. ## Examples of Graph Data Graphs are versatile and can represent various types of data: ### Social Networks Social networks are naturally represented as graphs, where nodes are users and edges represent connections between them (e.g., friendships, follows). Node features can include user profiles, while edge features can describe the nature of the relationship. ### Molecular Structures Molecules can be represented as graphs, with atoms as nodes and bonds as edges. Node features can describe atom type, charge, etc., while edge features can represent bond type and strength. This representation is crucial in fields like drug discovery and materials science, where understanding molecular structure is essential for predicting properties and interactions. ### Representing Images as Graphs Images can be represented as graphs, although this is less common due to the success of specialized models like convolutional neural networks. One possible approach is to represent pixels as nodes and connect neighboring pixels with edges, forming a grid-like graph. However, the regularity of this structure is often better handled by CNNs. Another approach is to segment the image into regions (superpixels) and represent these regions as nodes, with edges connecting adjacent regions. This can be useful for tasks like image segmentation or object recognition. ### Representing Text as Graphs Text can be represented as a graph where words are nodes and connections represent relationships between words, such as syntactic dependencies or co-occurrence in a sentence. However, the effectiveness of this approach compared to specialized models like transformers is debated, as transformers are specifically designed to capture sequential and contextual information in text. # Graph-Based Prediction Tasks GNNs can be used for various prediction tasks, depending on the level at which the prediction is made: node, edge, or the entire graph. ## Graph-Level Prediction Tasks In graph-level tasks, the goal is to predict a property of the entire graph. The prediction is based on the aggregated information from all nodes and edges within the graph. ::: tcolorbox - **Molecule Classification**: Predicting whether a molecule is toxic or has a specific pharmacological property (e.g., antibiotic, antiviral) based on its molecular graph structure. For example, given a graph representing the structure of a molecule, the task might be to predict if the molecule will smell pungent or not. - **Material Property Prediction**: Determining the stability, conductivity, or other physical properties of a material based on its atomic structure represented as a graph. - **Social Network Analysis**: Classifying a social network based on its overall characteristics, such as identifying a network as a community of sports enthusiasts or a political discussion group. For example, given the graph of a social network in Africa, predict global properties of this network. - **Program Analysis**: Predicting properties of a program's control flow graph, such as whether it contains certain types of bugs or security vulnerabilities. - **Drug Discovery**: Given the molecular graph of a drug, predict whether it will be effective against a specific disease. ::: **Example Visualization**: ::: center ::: ## Node-Level Prediction Tasks Node-level tasks involve predicting properties of individual nodes within a graph. The prediction for each node is based on its features and its relationship with neighboring nodes. ::: tcolorbox - **User Classification in Social Networks**: Predicting the demographics, interests, or preferences of a user in a social network based on their profile and connections. For example, predicting whether a user in the network will follow a particular user (e.g., \"High\" or \"John\") based on their connections and interactions. - **Node Role Identification**: Determining the role or function of a node in a network, such as identifying influential users in a social network or critical components in an infrastructure network. - **Protein Function Prediction**: Predicting the function of a protein in a protein-protein interaction network based on its interactions with other proteins. - **Fraud Detection**: Identifying suspicious users or accounts in a financial network based on their transaction patterns and connections. ::: **Example Visualization**: ::: center ::: ## Edge-Level Prediction Tasks Edge-level tasks focus on predicting properties of edges or the existence of edges within a graph. This can involve predicting the type of relationship between two nodes, the strength of the connection, or whether a connection should exist at all. ::: tcolorbox - **Link Prediction in Social Networks**: Predicting whether two users in a social network will become friends or whether a user will follow another user. - **Relationship Prediction**: Determining the type of relationship between two entities, such as predicting whether two people are colleagues, family members, or friends. - **Image Segmentation Relationship Prediction**: In an image segmented into regions, predicting the relationship between regions, such as whether one region is \"part of\" another or whether two regions are \"adjacent to\" each other. For example, given an image, extract the semantic segmentation and then predict the relationship between the entities in the image. - **Knowledge Graph Completion**: Predicting missing relationships between entities in a knowledge graph. ::: **Example Visualization**: ::: center ::: # Graph Neural Network Architecture ## Overall Structure and Workflow A Graph Neural Network (GNN) takes a graph $G = (V, E)$ as input, where $V$ represents the set of nodes and $E$ represents the set of edges. It processes the graph through a series of layers (or blocks), as illustrated in Figure [4](#fig:gnn_workflow){reference-type="ref" reference="fig:gnn_workflow"}. Each layer transforms the graph's features while preserving its underlying structure. The output is a transformed graph with updated node, edge, and/or global features. <figure id="fig:gnn_workflow"> <figcaption>GNN Workflow: Input graph is processed through multiple GNN layers, resulting in a transformed graph with updated features.</figcaption> </figure> The connectivity of the graph remains the same throughout the process; that is, the set of nodes $V$ and edges $E$ are unchanged. However, the features associated with nodes ($X$), edges ($E$), and the global graph ($u$) are updated by each GNN layer. ## The Message Passing Paradigm The core of GNN operation is the \*\*message-passing paradigm\*\*. In this paradigm, nodes update their embeddings (feature representations) by iteratively aggregating information from their neighbors. This process can be visualized as nodes sending \"messages\" to each other, where each message carries information about the sender's current state. ### Updating Node Embeddings via Message Passing In a single message-passing step, each node $v_i$ updates its embedding $x_i^{(l+1)}$ at layer $l+1$ by considering its own current embedding $x_i^{(l)}$ at layer $l$ and the embeddings of its neighbors $x_j^{(l)}$, where $j \in \mathcal{N}(i)$ and $\mathcal{N}(i)$ denotes the set of neighbors of node $i$. ### Neighborhood Aggregation Techniques The aggregation of information from neighboring nodes can be done using various methods. Common aggregation functions include: - **Sum**: Summing the embeddings of neighboring nodes: $\sum_{j \in \mathcal{N}(i)} x_j^{(l)}$ - **Mean**: Averaging the embeddings of neighboring nodes: $\frac{1}{|\mathcal{N}(i)|} \sum_{j \in \mathcal{N}(i)} x_j^{(l)}$ - **Max**: Taking the element-wise maximum of neighboring node embeddings: $\max_{j \in \mathcal{N}(i)} x_j^{(l)}$ - **Attention-based**: Using an attention mechanism to weigh the importance of each neighbor's contribution, as described in Graph Attention Networks (GATs). ### Transformation with Neural Networks After aggregating the neighborhood information, a neural network is applied to transform the aggregated embedding. This introduces non-linearity and allows the model to learn complex patterns in the graph data. The update rule for node $v_i$ at layer $l+1$ can be generally expressed as: $$x_i^{(l+1)} = f^{(l+1)}\left(x_i^{(l)}, \text{AGGREGATE}\left(\{x_j^{(l)} : j \in \mathcal{N}(i)\}\right)\right)$$ where: - $x_i^{(l+1)}$ is the updated embedding of node $v_i$ at layer $l+1$. - $x_i^{(l)}$ is the embedding of node $v_i$ at layer $l$. - $\mathcal{N}(i)$ is the set of neighbors of node $i$. - $\text{AGGREGATE}$ is an aggregation function (e.g., sum, mean, max). - $f^{(l+1)}$ is a neural network specific to layer $l+1$, which transforms the concatenated or combined embeddings. ## Pooling Strategies for Making Predictions After applying several GNN layers, we obtain a transformed graph with updated embeddings. To make predictions, we need to use these embeddings. The strategy for using these embeddings depends on the type of prediction task. ### Node-Level Prediction For node-level tasks, we can directly use the final node embeddings. A classifier (e.g., a neural network) can be applied to each node's embedding to predict its label or property. :::: algorithm ::: algorithmic **Input**: Transformed graph $G_N = (V, E, X_N, E_N, u_N)$, Classifier $C$ **Output**: Node predictions $y_i$ for each node $i \in V$ $y_i = C(x_i^N)$ ::: :::: ### Pooling from Edges to Nodes for Node-Level Prediction When node-level predictions are needed, but only edge information is available, we can aggregate information from edges to create node embeddings. This process is called \*\*edge-to-node pooling\*\*. :::: algorithm ::: algorithmic **Input**: Graph $G = (V, E)$, Edge embeddings $e_{ij}$ for each edge $(i, j) \in E$ **Output**: Node embeddings $x_i$ for each node $i \in V$ Initialize an empty set $S_i$ Add $e_{jk}$ to $S_i$ $x_i = \text{AGGREGATE}(S_i)$ ::: :::: The complexity of this algorithm is $O(|V| + |E|)$, as we iterate through all nodes and edges in the worst case. ### Pooling from Nodes to Edges for Edge-Level Prediction Similarly, when edge-level predictions are needed, but only node information is available, we can aggregate node embeddings to create edge embeddings. This is called \*\*node-to-edge pooling\*\*. :::: algorithm ::: algorithmic **Input**: Graph $G = (V, E)$, Node embeddings $x_i$ for each node $i \in V$ **Output**: Edge embeddings $e_{ij}$ for each edge $(i, j) \in E$ $e_{ij} = \text{COMBINE}(x_i, x_j)$ ::: :::: The complexity of this algorithm is $O(|E|)$, as we iterate through all edges. ### Pooling for Global Graph-Level Prediction To make predictions about the entire graph, we need to create a global graph embedding. This can be achieved by aggregating node or edge embeddings. This process is called \*\*graph-level pooling\*\*. :::: algorithm ::: algorithmic **Input**: Graph $G = (V, E)$, Node embeddings $x_i$ for each node $i \in V$ **Output**: Global graph embedding $u$ Initialize an empty set $S$ Add $x_i$ to $S$ $u = \text{AGGREGATE}(S)$ ::: :::: The complexity of this algorithm is $O(|V|)$, as we iterate through all nodes. ::: mdframed **Note:** The choice of aggregation function (AGGREGATE) and combination function (COMBINE) depends on the specific task and the nature of the data. Also, after applying pooling strategies, a classifier can be used to make the final prediction. For example, after graph-level pooling, a neural network can be used to predict the graph's label. ::: # Message Passing Implementation ## Representing Graph Data for Computation To implement message passing in a GNN, we need efficient ways to represent the graph structure and the features associated with its nodes and edges. ### Node Embeddings Each node $v_i \in V$ is represented by an embedding vector $x_i \in \mathbb{R}^{d}$, where $d$ is the dimensionality of the embedding space. This vector encodes the features of the node. For a graph with $n$ nodes, we can represent all node embeddings as a matrix $X \in \mathbb{R}^{n \times d}$, where each row corresponds to the embedding of a node. ### Adjacency Matrix Representation The adjacency matrix $A \in \mathbb{R}^{n \times n}$ is a square matrix that encodes the connections between nodes in the graph. It is defined as: $$A_{ij} = \begin{cases} 1, & \text{if } (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases}$$ where $A_{ij}$ is the element in the $i$-th row and $j$-th column of $A$, and $(v_i, v_j) \in E$ indicates the presence of an edge between nodes $v_i$ and $v_j$. ### Degree Matrix Representation The degree matrix $D \in \mathbb{R}^{n \times n}$ is a diagonal matrix where each diagonal element $D_{ii}$ represents the degree of node $v_i$, which is the number of edges connected to it. Formally: $$D_{ii} = \sum_{j=1}^{n} A_{ij}$$ ## Challenges with Basic Aggregation Methods While the basic message-passing idea is powerful, straightforward implementations can face certain challenges: ### Lack of Self-Information in Aggregation A simple aggregation of neighbor embeddings, such as $\sum_{j \in \mathcal{N}(i)} x_j$, might ignore the node's own features during the update. This can lead to a loss of information about the node itself. For example, if we only consider the neighbors' embeddings, the updated embedding of a node might not reflect its initial features, leading to a misrepresentation of the node's identity in the graph. ### Potential for Exploding Values Repeatedly summing embeddings across multiple message-passing layers can lead to very large values in the node embeddings. This can cause numerical instability during training and negatively impact the model's performance. Specifically, if the sum of embeddings is not normalized, the magnitude of the embeddings can grow exponentially with each layer, making the optimization process unstable. ## Addressing the Challenges ### Incorporating Self-Connections To ensure that a node's own features are considered during aggregation, we can add self-loops to the graph. This is achieved by adding the identity matrix $I$ to the adjacency matrix $A$, creating a new adjacency matrix $\tilde{A}$: $$\tilde{A} = A + \lambda I$$ Here, $\lambda$ is a hyperparameter that controls the weight given to the node's own features. When $\lambda = 1$, it's equivalent to adding a single self-loop to each node. Now, when aggregating neighbor information, the node's own embedding will also be included in the sum, weighted by $\lambda$. ### Normalization using the Degree Matrix To prevent the explosion of values during repeated aggregation, we can normalize the aggregation by the node degrees. A common approach is to multiply the adjacency matrix by theinverse of the degree matrix. This leads to a normalized adjacency matrix: $$\hat{A} = D^{-1}A$$ Now, instead of summing the neighbor embeddings, we are effectively taking their average. More advanced normalization techniques, such as the one used in Graph Convolutional Networks (GCNs), use a symmetrically normalized adjacency matrix: $$\hat{A} = D^{-\frac{1}{2}} \tilde{A} D^{-\frac{1}{2}}$$ This normalization considers both the degree of the central node and the degrees of its neighbors. The use of $D^{-\frac{1}{2}}$ on both sides helps to scale the embeddings proportionally to the square root of thenode degrees, which can further stabilize training. ::: tcolorbox Let's consider a simple message-passing update rule using the normalized adjacency matrix with self-connections: $$X^{(l+1)} = \sigma(\hat{A} X^{(l)} W^{(l)})$$ where: - $X^{(l)}$ is the matrix of node embeddings at layer $l$. - $W^{(l)}$ is the weight matrix for layer $l$. This matrix is learned during training and transforms the aggregated embeddings. - $\sigma$ is an activation function (e.g., ReLU). - $\hat{A} = D^{-\frac{1}{2}} (A + I) D^{-\frac{1}{2}}$ is the normalized adjacency matrix with self-connections. This update rule first adds self-connections to the graph, then normalizes the adjacency matrix, performs a weighted aggregation of neighbor embeddings (including the node's own), and finally applies a non-linear transformation using the learned weight matrix $W^{(l)}$. ::: ## Iterative Message Passing and Neighborhood Scope By iteratively applying message passing, the model can propagate information across the graph. Each iteration allows nodes to incorporate information from a wider neighborhood. After $k$ iterations, a node's embedding will contain information from nodes that are at most $k$ hops away in the graph. <figure id="fig:neighborhood_scope"> <figcaption>Neighborhood scope after k iterations of message passing, starting from node 1.</figcaption> </figure> ::: mdframed **Note:** The number of message-passing iterations is a hyperparameter that needs to be tuned. Using too few iterations might limit the model's ability to capture long-range dependencies, while using too many iterations can lead to over-smoothing, where node embeddings become too similar and lose their discriminative power. In practice, 2-4 layers are often sufficient based on empirical evidence. ::: ## A Concrete Example Let's consider a graph with 5 nodes and the following adjacency matrix $A$, degree matrix $D$, and initial node embeddings matrix $X^{(0)}$: $$A = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix}, D = \begin{bmatrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}, X^{(0)} = \begin{bmatrix} -1.5 & 1.1 & 2.5 \\ 3.1 & -2.6 & 2.7 \\ -0.3 & 1.7 & -2.0 \\ 1.9 & -0.5 & 0.8 \\ 2.2 & -1.3 & 0.5 \end{bmatrix}$$ We'll add self-loops ($\tilde{A} = A + I$) and compute the symmetrically normalized adjacency matrix: $$\tilde{A} = A + I = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}$$ $$\tilde{D} = \begin{bmatrix} 3 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{bmatrix}$$ $$\hat{A} = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$$ We won't compute the exact values of $\hat{A}$ here, but it will be a 5x5 matrix. Now, let's perform one step of message passing using the formula: $$X^{(1)} = \sigma(\hat{A} X^{(0)} W^{(0)})$$ Suppose we have a randomly initialized weight matrix $W^{(0)} \in \mathbb{R}^{3 \times 2}$: $$W^{(0)} = \begin{bmatrix} 0.5 & -0.2 \\ -0.3 & 0.4 \\ 0.1 & -0.1 \end{bmatrix}$$ We first compute the product $\hat{A} X^{(0)}$. This will result in a 5x3 matrix where each row represents the aggregated and normalized embedding of a node, considering its neighbors and itself. Then, we multiply this matrix by $W^{(0)}$ to get a 5x2 matrix. Finally, we apply an activation function $\sigma$ (e.g., ReLU) element-wise to obtain $X^{(1)}$. After computing $X^{(1)}$, we can use it for node-level predictions or perform further message-passing steps. # Conclusion Graph Neural Networks offer a powerful way to analyze and make predictions on graph-structured data. They leverage the inherent structure of graphs to capture complex relationships between entities, making them suitable for a wide range of applications, from social network analysis to drug discovery. Key takeaways from this lecture include: - GNNs process data in a non-linear fashion, determined by the graph structure. - Information can be encoded at the node, edge, and graph levels. - GNNs can perform various prediction tasks at different levels of the graph. - The message-passing paradigm is central to GNN operation, allowing nodes to update their embeddings based on their neighbors. - Pooling strategies enable predictions at different levels by aggregating information. - Challenges like the lack of self-information and exploding values can be addressed through techniques like adding self-connections and normalization. \*\*Follow-up Questions:\*\* - How might the choice of aggregation function (e.g., sum, mean, max) impact the performance of a GNN? - What are the trade-offs between using a deep GNN (many layers) versus a shallow one? - How can GNNs be adapted to handle directed graphs or graphs with multiple types of edges? - What are some real-world applications where GNNs have shown significant improvements over traditional methods? This concludes the lecture on Graph Neural Networks. Further exploration and experimentation with different architectures and applications will deepen your understanding of this fascinating field.